"""

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
"""

def lengthOfLIS(nums):

    max_length = 1
    for i in range(len(nums)):
        show_str = [nums[i]]
        cur_length = 1
        local_max = nums[i]
        for j in range(i, len(nums)):
            if local_max < nums[j]:
                local_max = nums[j]
                cur_length+=1
                show_str.append(nums[j])
        print(show_str)
        if cur_length> max_length:
            print("比记录的长度还长, 进行替换")
            max_length = cur_length
    return max_length
def lengthOfLIS1(nums):
    nums_max = []
    for i,num1 in enumerate(nums):
        for j,num2 in enumerate(nums_max,start=i):
            if num1 < num2:
                nums_max[i]+=1


print(lengthOfLIS([10, 9, 2, 5, 3, 4, 101, 18]))
# assert lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]), 4